This invention relates in general to the timing of intervals in a computer and more specifically to a system providing an interval timing service for processes running in a computer system.
Different types of interval timers can be found in alarm clocks, egg timers, or timers in VCRs. Interval timers are used to cause an alarm or other pre-determined action to occur after a pre-specified amount of time. Within computer systems, interval timers are used in communications over networks, such as for re-transmitting a packet of communications data when a response does not arrive within the expected amount of time. Interval timers are also used in interactions with hardware devices, for error detection and handling, for detecting and handling failures within fault-tolerant systems, for pacing the rate at which displays are updated, in interactions with human beings, for dividing xe2x80x9cCPU timexe2x80x9d equitably among computer processes, and for a wide variety of other uses.
Some computer systems require the maintenance, or scheduling, of many events that are controlled by an interval timer or timers. Various schemes have been adopted to improve the efficiency of such timers and scheduling because the processing overhead required to update the timers and handle the events can become significant and degrade the ability of the computer to handle other tasks. An example of an approach to handling multiple timers is described in a paper by G. Varghese and T. Lauck entitled xe2x80x9cHashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility,xe2x80x9d Proceedings of the Eleventh ACM Symposium on Operating System Principles, 8-11 November 1987, Operating System Review 21 (5), ACM Press, 1987, ISBN 0-89791-242-X.
The system described by Varghese and Lauck, places emphasis on a xe2x80x9cTimer Startxe2x80x9d function. In accordance with Varghese and Lauck the timing method can be described by use of a hierarchy of timing wheels using xe2x80x9choursxe2x80x9d xe2x80x9cminutesxe2x80x9d and xe2x80x9csecondsxe2x80x9d wheels to time delays of up to 24 hours with one-second resolution. This could be part of a larger hierarchy of timing wheels, allowing timing, for example, for up to 16 weeks.
For example, Varghese and Lauck consider the case where the current time is 10:24:30 and an interval of 50 minutes and 45 seconds is to be timed.
In the following:
curTime is the current time, or some regularly updated similar value. Since we are only interested in measuring intervals of time, curTime need not be the same as the true current time, it only needs to be advancing at the same rate. Also, it need not be directly updated by timing hardware, but it must be possible to access the timing hardware in order to learn the correct value for curTime.
timeoutValue is the specified amount of time to elapse before the timer expires.
expirationTime is the time at which the timer is to expire, if not previously canceled. That is, the timer expires when curTime becomes equal to expirationTime.
The method for Timer Start is one of first computing the expiration time, and then enqueuing (chaining) the timer on the most-significant wheel for which the expiration time differs from the current time:
According to this prior method, the timer will be chained on the hours wheel in slot 11. This happens because expirationTime differs from curTime in the hours position, and the hours portion of expirationTime is 11.
Then, if the client doesn""t cancel the timer, at 11:00:00 the timer will be moved to slot 15 of the minutes wheel. At 11:15:00, the timer is moved again, to slot 15 of the seconds wheel. The timer finally expires at 11:15:15 and is no longer on any slot of any timing wheel, until it""s re-used to time another interval of time.
Although Varghese and Lauck describe a relatively efficient timer processing mechanism, it is desirable to provide a timer system that further reduces the processing required by a computer to operate and maintain the timers.
The present invention provides a timer system that uses less computer time than previous processes and methods, leaving more computer time available to do other work. Multiple timing wheels are maintained with slots associated with each wheel. In one embodiment, a process, event, or other item that needs to be timed is scheduled on a slot on a timing wheel according to the timeout value of the item. In another embodiment, the wheels have a maximum timeout value associated with them. The maximum timeout value is used to schedule the item. In another embodiment, the maximum timeout value for a wheel is increased to be an integral multiple of the period of the wheel before scheduling according to the maximum timeout value is performed.